package com.cg.offer;

import com.cg.leetcode.TreeNode;
import org.junit.Test;

/**
 * 剑指Offer 54.二叉搜索树的第k大节点
 *
 * @program: LeetCode->Offer_54
 * @description: 剑指Offer 54.二叉搜索树的第k大节点
 * @author: cg
 * @create: 2022-03-23 20:32
 **/
public class Offer_54 {

    @Test
    public void test54() {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);

        root.right = new TreeNode(6);
        System.out.println(kthLargest(root, 3));
    }

    /**
     * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
     * <p>
     * 示例 1:
     * 输入: root = [3,1,4,null,2], k = 1
     * 3
     * / \
     * 1   4
     * \
     * 2
     * 输出: 4
     * <p>
     * 示例 2:
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     * 5
     * / \
     * 3   6
     * / \
     * 2   4
     * /
     * 1
     * 输出: 4
     * <p>
     * 限制：
     * 1 ≤ k ≤ 二叉搜索树元素个数
     *
     * @param root
     * @param k
     * @return
     */
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    int res, k;

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        if (k == 0) {
            return;
        }
        if (--k == 0) {
            res = root.val;
        }
        dfs(root.left);
    }

    /*public int kthLargest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        dfs(root, k);
        return list.get(list.size() - k);
    }

    List<Integer> list = new ArrayList<>();

    public void dfs(TreeNode root, int k) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left, k);
        }
        list.add(root.val);
        if (root.right != null) {
            dfs(root.right, k);
        }
    }*/

}
